(* Flatten a nested list structure. *)

(* There is no nested list type in Objective Caml, so we need to define
   one first. A node of a nested list is either an element, or a list
   of nodes. *)

(* 类型定义：
  'a node 是一个递归类型，表示两种节点
  One of 'a 单个元素节点
  Many of 'a node list 包含多个子节点的复合节点*)
type 'a node = 
    One of 'a
  | Many of 'a node list
;;

(* The example from the problem: (a (b (c d) e)) *)

let example = 
  [ One `a ; Many [ One `b ; Many [ One `c ; One `d ] ; One `e ] ]
;;

(* This function traverses the list, prepending any encountered elements
   to an accumulator, which flattens the list in inverse order. It can then
   be reversed to obtain the actual flattened list. *)

let flatten list = 
  let rec aux acc = function
    | [] -> acc
    | One x :: t -> aux (x :: acc) t  (* One x节点：将x加入累加器，继续处理剩余部分 *)
    | Many l :: t -> aux (aux acc l) t (* Many l节点：先递归处理子列表l，再处理剩余部分 *)
  in
  List.rev (aux [] list) (* 结果用List.rev反转，因为累加器是反向构建的 *)
;;

(* 先处理One "a" → ["a"]
  处理Many节点，递归处理其子列表：
  One "b" → ["b"]
  Many [One "c"; One "d"] → 递归得到["c"; "d"]
  One "e" → ["e"]
  合并子结果 → ["b"; "c"; "d"; "e"]
  合并主结果 → ["a"; "b"; "c"; "d"; "e"] *)
assert (flatten example = [ `a ; `b ; `c ; `d ; `e ])

